/**
 * @author zjkermit
 * @email zjkermit@gmail.com
 * @date May 21, 2014
 */
package zhoujian.oj.leetcode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;

import org.junit.Test;

/**
 * @version 1.0
 * @description Given two words (start and end), and a dictionary, find all
 *              shortest transformation sequence(s) from start to end, such
 *              that:
 * 
 *              Only one letter can be changed at a time
 * 
 *              Each intermediate word must exist in the dictionary
 * 
 * 
 *              For example,
 * 
 *              Given:
 * 
 *              start = "hit"
 * 
 *              end = "cog"
 * 
 *              dict = ["hot","dot","dog","lot","log"]
 * 
 *              Return
 * 
 *              [ ["hit","hot","dot","dog","cog"],
 *              ["hit","hot","lot","log","cog"] ]
 * 
 *              Note:
 * 
 *              All words have the same length. All words contain only lowercase
 *              alphabetic characters.
 */
public class WordLadderII {
	
	public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) {
		ArrayList<ArrayList<String>> res = new ArrayList<>();
		ArrayList<String> tmp = new ArrayList<>();
		tmp.add(start);
		ArrayDeque<String> queue = new ArrayDeque<String>();
		ArrayDeque<ArrayList<String>> que = new ArrayDeque<>();
		Iterator<String> it;
		queue.push(start);
		que.add(tmp);
		while (!queue.isEmpty()) {
			String s = queue.pop();
			tmp = que.pop();
			
			if (helper(s, end)) {
				if (res.isEmpty()) {
					tmp.add(end);
					res.add(tmp);
				} else if (res.get(0).size() - 1 == tmp.size()) {
					tmp.add(end);
					res.add(tmp);
				}
				continue;
			}

			it = dict.iterator();
			while (it.hasNext()) {
				String ss = it.next();
				if (helper(s, ss)) {
					queue.add(ss);
					ArrayList<String> tt = new ArrayList<>(tmp);
					tt.add(ss);
					que.add(tt);
					it.remove();
				}
			}
		}

		return res;
    }
	
	private boolean helper(String s1, String s2) {
		int count = 0;
		for (int i = 0; i < s1.length(); ++i) {
			if (count > 1)
				return false;
			if (s1.charAt(i) != s2.charAt(i))
				++count;
		}
		return count == 1;
	}
	
	@Test
	public void test0() {
		HashSet<String> dict = new HashSet<String>();
		dict.add("hot");
		dict.add("cog");
		dict.add("dog");
		dict.add("tot");
		dict.add("hog");
		dict.add("hop");
		dict.add("pot");
		dict.add("dot");

		System.out.println(findLadders("hot", "dog", dict));
	}

	@Test
	public void test1() {
		HashSet<String> dict = new HashSet<String>();
		String[] arr = { "hot","dot","dog","lot","log" };
		for (String s : arr)
			dict.add(s);

		System.out.println(findLadders("hit", "cog", dict));
	}

	@Test
	public void test2() {
		HashSet<String> dict = new HashSet<String>();
		String[] arr = { "si", "go", "se", "cm", "so", "ph", "mt", "db", "mb",
				"sb", "kr", "ln", "tm", "le", "av", "sm", "ar", "ci", "ca",
				"br", "ti", "ba", "to", "ra", "fa", "yo", "ow", "sn", "ya",
				"cr", "po", "fe", "ho", "ma", "re", "or", "rn", "au", "ur",
				"rh", "sr", "tc", "lt", "lo", "as", "fr", "nb", "yb", "if",
				"pb", "ge", "th", "pm", "rb", "sh", "co", "ga", "li", "ha",
				"hz", "no", "bi", "di", "hi", "qa", "pi", "os", "uh", "wm",
				"an", "me", "mo", "na", "la", "st", "er", "sc", "ne", "mn",
				"mi", "am", "ex", "pt", "io", "be", "fm", "ta", "tb", "ni",
				"mr", "pa", "he", "lr", "sq", "ye" };
		for (String s : arr)
			dict.add(s);

		System.out.println(findLadders("qa", "sq", dict));
	}

	@Test
	public void test3() {
		HashSet<String> dict = new HashSet<String>();
		String[] arr = { "dose", "ends", "dine", "jars", "prow", "soap",
				"guns", "hops", "cray", "hove", "ella", "hour", "lens", "jive",
				"wiry", "earl", "mara", "part", "flue", "putt", "rory", "bull",
				"york", "ruts", "lily", "vamp", "bask", "peer", "boat", "dens",
				"lyre", "jets", "wide", "rile", "boos", "down", "path", "onyx",
				"mows", "toke", "soto", "dork", "nape", "mans", "loin", "jots",
				"male", "sits", "minn", "sale", "pets", "hugo", "woke", "suds",
				"rugs", "vole", "warp", "mite", "pews", "lips", "pals", "nigh",
				"sulk", "vice", "clod", "iowa", "gibe", "shad", "carl", "huns",
				"coot", "sera", "mils", "rose", "orly", "ford", "void", "time",
				"eloy", "risk", "veep", "reps", "dolt", "hens", "tray", "melt",
				"rung", "rich", "saga", "lust", "yews", "rode", "many", "cods",
				"rape", "last", "tile", "nosy", "take", "nope", "toni", "bank",
				"jock", "jody", "diss", "nips", "bake", "lima", "wore", "kins",
				"cult", "hart", "wuss", "tale", "sing", "lake", "bogy", "wigs",
				"kari", "magi", "bass", "pent", "tost", "fops", "bags", "duns",
				"will", "tart", "drug", "gale", "mold", "disk", "spay", "hows",
				"naps", "puss", "gina", "kara", "zorn", "boll", "cams", "boas",
				"rave", "sets", "lego", "hays", "judy", "chap", "live", "bahs",
				"ohio", "nibs", "cuts", "pups", "data", "kate", "rump", "hews",
				"mary", "stow", "fang", "bolt", "rues", "mesh", "mice", "rise",
				"rant", "dune", "jell", "laws", "jove", "bode", "sung", "nils",
				"vila", "mode", "hued", "cell", "fies", "swat", "wags", "nate",
				"wist", "honk", "goth", "told", "oise", "wail", "tels", "sore",
				"hunk", "mate", "luke", "tore", "bond", "bast", "vows", "ripe",
				"fond", "benz", "firs", "zeds", "wary", "baas", "wins", "pair",
				"tags", "cost", "woes", "buns", "lend", "bops", "code", "eddy",
				"siva", "oops", "toed", "bale", "hutu", "jolt", "rife", "darn",
				"tape", "bold", "cope", "cake", "wisp", "vats", "wave", "hems",
				"bill", "cord", "pert", "type", "kroc", "ucla", "albs", "yoko",
				"silt", "pock", "drub", "puny", "fads", "mull", "pray", "mole",
				"talc", "east", "slay", "jamb", "mill", "dung", "jack", "lynx",
				"nome", "leos", "lade", "sana", "tike", "cali", "toge", "pled",
				"mile", "mass", "leon", "sloe", "lube", "kans", "cory", "burs",
				"race", "toss", "mild", "tops", "maze", "city", "sadr", "bays",
				"poet", "volt", "laze", "gold", "zuni", "shea", "gags", "fist",
				"ping", "pope", "cora", "yaks", "cosy", "foci", "plan", "colo",
				"hume", "yowl", "craw", "pied", "toga", "lobs", "love", "lode",
				"duds", "bled", "juts", "gabs", "fink", "rock", "pant", "wipe",
				"pele", "suez", "nina", "ring", "okra", "warm", "lyle", "gape",
				"bead", "lead", "jane", "oink", "ware", "zibo", "inns", "mope",
				"hang", "made", "fobs", "gamy", "fort", "peak", "gill", "dino",
				"dina", "tier" };
		for (String s : arr)
			dict.add(s);

		System.out.println(findLadders("nape", "mild", dict));
	}

	

}
